#
# @lc app=leetcode.cn id=106 lang=python3
#
# [106] 从中序与后序遍历序列构造二叉树
#
from typing import List


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
# @lc code=start
# Definition for a binary tree node.

class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
        if len(inorder) == 0:
            return None
        return self.helpBuilder(inorder, postorder, 0, len(inorder), 0, len(postorder))
        
    def helpBuilder(self, inorder, postorder, in_start, in_end, post_start, post_end):
        if in_start == in_end:
            return None
        root_val = postorder[post_end-1]
        root_idx = inorder.index(root_val)
        root = TreeNode(root_val)
        left_length = root_idx - in_start
        root.left = self.helpBuilder(inorder, postorder, in_start, root_idx, post_start, post_start+left_length)
        root.right = self.helpBuilder(inorder, postorder, root_idx+1, in_end, post_start+left_length, post_end-1)
        return root
# @lc code=end

